//
// Shell Sort
// Created by Win10 on 2023/4/7.
//

#ifndef C_DATA_STRUCTURE_SHELL_SORT_H
#define C_DATA_STRUCTURE_SHELL_SORT_H


#include <algorithm>

template<typename T>
//整数或浮点数皆可使用
void shell_sort(T a[], int len) {
  int i, j, gap;
  // gap为步长，每次减为原来的一半。
  for (gap = len / 2; gap > 0; gap /= 2) {
    // 共gap个组，对每一组都执行直接插入排序
    for (i = 0; i < gap; i++) {
      for (j = i + gap; j < len; j += gap) {
        // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
        if (a[j] < a[j - gap]) {
          T tmp = a[j];
          int k = j - gap;
          while (k >= 0 && a[k] > tmp) {
            a[k + gap] = a[k];
            k -= gap;
          }
          a[k + gap] = tmp;
        }
      }
    }
  }
}

#endif //C_DATA_STRUCTURE_SHELL_SORT_H
